#include <bits/stdc++.h>

using namespace std;

// 单词搜索
// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word
// 如果 word 存在于网格中，返回 true ；否则，返回 false 。
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成
// 其中"相邻"单元格是那些水平相邻或垂直相邻的单元格
// 同一个单元格内的字母不允许被重复使用
// 测试链接 : https://leetcode.cn/problems/word-search/

class Solution 
{
private:
    int m, n;

    // 因为 board 会改其中的字符
	// 用来标记哪些字符无法再用
	// 带路径的递归无法改成动态规划或者说没必要
	// 从(i,j)出发，来到word[k]，请问后续能不能把word走出来
    bool f(vector<vector<char>>& board, string word, int i, int j, int k)
    {
        if(k == word.size()) return true;
        if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) return false;

        char tmp = board[i][j];
        board[i][j] = 0;
        // 不越界，b[i][j] == word[k]
        bool ans = f(board, word, i - 1, j, k + 1)
                || f(board, word, i + 1, j, k + 1)
                || f(board, word, i, j - 1, k + 1)
                || f(board, word, i, j + 1, k + 1);
        board[i][j] = tmp;
        return ans;
    }

public:
    bool exist(vector<vector<char>>& board, string word) 
    {
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(f(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
};


class Solution 
{
private:
    int m, n;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool visited[7][7];

    bool dfs(vector<vector<char>>& board, string& word, int index, int i, int j)
    {
        if(index == word.size()) return true;

        for(int k = 0; k < 4; ++k)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && board[x][y] == word[index])
            {
                visited[x][y] = true;
                if(dfs(board, word, index + 1, x, y)) return true;
                visited[x][y] = false;
            }
        }
        return false;
    }

public:
    bool exist(vector<vector<char>>& board, string word) 
    {
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == word[0])
                {
                    visited[i][j] = true;
                    if(dfs(board, word, 1, i, j)) return true;
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }
};